


# 343. 整数拆分

def integerBreak(n):
    """
    :type n: int
    :rtype: int
    """
    dp = [None] * (n + 1)
    dp[1] = 1
    dp[2] = 1
    if n == 1:
        return 0
    if n == 2:
        return 1
    for i in range(3, n+1):
        temp = []
        for j in range(1, i):
            temp.append(max(dp[i - j],i-j) * max(dp[j],j))
        dp[i] = max(temp)
    return dp[n]

if __name__ == "__main__":
    print(integerBreak(10))